Search results for "L-attributed grammar"

showing 3 items of 3 documents

Grammars++ for modelling information in text

1999

Abstract Grammars provide a convenient means to describe the set of valid instances in a text database. Flexibility in choosing a grammar can be exploited to provide information modelling capability by designing productions in the grammar to represent entities and relationships of interest to database applications. Additional constraints can be specified by attaching predicates to selected nonterminals in the grammar. When used for database definition, grammars can provide the functionality that users have come to expect of database schemas. Extended grammars can also be used to specify database manipulation, including query, update, view definition, and index specification.

Computer scienceViewmedia_common.quotation_subjectComputerApplications_COMPUTERSINOTHERSYSTEMScomputer.software_genreQuery languageDatabase designAdaptive grammarRule-based machine translationmedia_commonGrammarProgramming languagebusiness.industryDatabase schemaPredicate (grammar)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESExtended Affix GrammarHardware and ArchitectureAffix grammarStochastic context-free grammarSynchronous context-free grammarArtificial intelligenceL-attributed grammarbusinesscomputerSoftwareNatural language processingInformation SystemsInformation Systems
researchProduct

The complexity of graph languages generated by hyperedge replacement

1990

Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.

ParsingTheoretical computer scienceComputer Networks and CommunicationsComputer sciencebusiness.industryComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Parsing expression grammarcomputer.software_genreTop-down parsingTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESParser combinatorS-attributed grammarTop-down parsing languageArtificial intelligenceL-attributed grammarbusinesscomputerComputer Science::Formal Languages and Automata TheorySoftwareNatural language processingInformation SystemsBottom-up parsingActa Informatica
researchProduct

Using Attribute Grammars for Description of Inductive Inference Search Space

1998

The problem of practically feasible inductive inference of functions or other objects that can be described by means of an attribute grammar is studied in this paper. In our approach based on attribute grammars various kinds of knowledge about the object to be found can be encoded, ranging from usual input/output examples to assumptions about unknown object's syntactic structure to some dynamic object's properties. We present theoretical results as well as describe the architecture of a practical inductive synthesis system based on theoretical findings.

business.industryComputer scienceAttribute grammarInferenceContext-free grammarInductive reasoningcomputer.software_genreObject (computer science)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESRule-based machine translationTerminal and nonterminal symbolsFormal languageSyntactic structureArtificial intelligenceL-attributed grammarbusinesscomputerNatural language processing
researchProduct